This invention is useful in signal processing.
The basic concept behind the invention is to take an expression for a long discrete cosine transform and to break it into smaller parts, four smaller parts, using four modules, which are evaluated by the same kind of operation. The critical part is that, in order to break it into smaller parts, complex multiplications have to be utilized. Use is made of the fact that the exponential function has an addition theorem, namely, e.sup.ia e.sup.ib = e.sup.i(a.sup.+b). The cosine function has a more complicated addition theorem.
This invention involves working through complete Fourier transforms and then taking the real parts when the operation is all done, rather than taking the real parts at an early stage, as is generally done in the prior art. The prior art process does not permit separation into simpler operations.
In order to calculate the equivalent of a discrete Fourier transform of a mirror symmetry extended data block, it is not necessary to generate the physical replicas of the image mirror points.
That is, the data points do not have to be physically replicated. In fact, the apparatus is designed to avoid the replication, since that would require extra memories and associated memory operations. The equivalent of taking the Fourier transform of an extended data block, extended in mirror symmetry, is equivalent mathematically to extending the real part of a Fourier transform so that it is partly filled with zeroes.
More specifically, this invention relates to apparatus for the implementation of the even discrete cosine transform (EDCT). The specific structure chosen permits the use of four EDFT modules to compute a double-length transform, with twice the throughput rate of the individual modules. If the EDFT is chosen to be used as a module for computing the EDCT, then more of the same modules may be used to perform a larger transform, a double length transform, as well as the shorter, regular length, module.
The utility of the EDCT for data compression has been described in the prior art. Reference is directed specifically to: [1] Means, R. W., Whitehouse, H. J., et al, Image Transmission Via Spread Spectrum Techniques, ARPA Quarterly Technical Report, March 1 - June 1, 1973, Order Number 2303, Code Number 3G10, published by the Naval Undersea Center, San Diego, Calif., 92106; [2] Means, R. W., Speiser, J. M., Whitehouse, H. J., et al, Image Transmission Via Spread Spectrum Techniques, ARPA Quarterly Technical Report, June 1 - Oct. 1, 1973, Order Number 2303, Code Number 3G10, the same publisher; and [3] Ahmed, N., Natarajan, T., and Rao, K. R., On Image Processing and a Discrete Cosine Transform, IEEE Transactions on Electronic Computers, Jan. 1974, pp. 90-93.
Several different serial-access implementations for high speed computation of the EDCT have also been described, for example, in the technical note [4] Speiser, J. M., entitled High Speed Serial Access Implementation For Discrete Cosine Transforms, NUC TN 1265, Jan. 8, 1974, published by the Naval Undersea Center, San Diego, Calif. 92106.
Implementations using charge coupled device (CCD) transversal filters are particularly attractive [2] for applications which require low weight, small size, low power consumption, and controllable clocking of the computation. Present CCD transversal filters perform well at shift rates of up to about 5 .times. 10.sup.6 samples per second. This is too slow by a factor of two to handle conventional television signals using the prior art EDCT architectures. This invention includes a subdivision of the computation tasks to permit greater parallelism in the hardware, to increase both the throughput and transform size implementable with a fixed set of transversal filter and chirp read-only memory modules.